﻿#include<iostream>
#include <queue>
#include <stack>
using namespace std;

//思路：每次输入数据时回转queue
//参考：http://blog.csdn.net/jiange_zh/article/details/50583370

template<class T> class Sta
{
public:
	void push(T t)
	{
       if(q1.empty())
	   {
		   q1.push(t);
		   while(!q2.empty())
		   {
			   q1.push(q2.front());
			   q2.pop();
		   }
	   }
	   else
	   {
		   q2.push(t);
		   while(!q1.empty())
		   {
		      q2.push(q1.front());
			  q1.pop();
		   }
	   }
	}
	void pop()
	{
		if(q1.empty()&&q2.empty())
			cerr<<"is empty!"<<endl;
		else if(q1.empty())
		{
			q2.pop();
		}
		else q1.pop();
	}
	T top()
	{
		if(q1.empty()&&q2.empty())
			cerr<<"is empty!"<<endl;
		else if(q1.empty())
		{
			return q2.front();
		}
		else return q1.front();
	}
private:queue<T> q1,q2; 
};


void main()
{
	Sta<int> q;
	q.push(1);
	q.push(2);
	q.push(3);
	cout<<q.top()<<endl;
	q.pop();
	cout<<q.top()<<endl;
	q.push(4);
	q.push(5);
	cout<<q.top()<<endl;
	q.pop();
	cout<<q.top()<<endl;
	q.pop();
	q.pop();
	q.pop();
	q.pop();


	stack<int> qq;
	qq.push(1);
	qq.push(2);
	qq.push(3);
	cout<<qq.top()<<endl;
	qq.pop();
	cout<<qq.top()<<endl;
	qq.push(4);
	qq.push(5);
	cout<<qq.top()<<endl;
	qq.pop();
	cout<<qq.top()<<endl;
	

}